1. Field of the Invention
This invention relates to a method and apparatus for generating routing information, including the generation of driving guides for display to a user.
2. Discussion of the Background
Navigational Aids built upon small portable, and powerful computers and specialized electronics have revolutionized the concept of maps and methods of finding routes from an origin to a specific destination. One recent breakthrough fueling this revolution is illustrated in FIG. 1, the concept of an automobile based map and direction finding system 100, as described in Loughmiller, Jr. et al., U.S. Pat. No. 4,914,605, issued Apr. 3, 1990, entitled xe2x80x9cApparatus and Method for Displaying a Map,xe2x80x9d incorporated herein by reference, in its entirety. Additional methods and navigation functionality are also described in Honey et al., U.S. Pat. No. 4,796,191, issued Jan. 03, 1989, entitled xe2x80x9cVEHICLE NAVIGATION SYSTEM AND METHOD,xe2x80x9d also incorporated herein by reference, in its entirety.
Such systems provide a map display 110 that is properly oriented so as to be easily read by a driver and provide navigational aid. Modern systems are end-point oriented and can provide a path to a specific destination. They usually include an option for a map, the ability to select a zoom factor, list turn by turn directions, and other options. Other specialized features of such systems include the ability to change a display of an area surrounding the driver as a location of the driver progresses, display a desired destination entered by the driver, and provide a symbol on the display indicating the current location of the driver.
A typical system involving maps with routes utilize a mathematical structure called a directed graph. A directed graph consists of a set of points called nodes, along with a set of connections called xe2x80x9clinks.xe2x80x9d
FIG. 2A shows an exemplar directed graph which shows eastbound oneway street 50 and two-way street 52, both intersecting with two-way street 54. Street 50 intersects with street 54 at intersection 60. Street 52 intersects with street 54 at intersection 70. At intersection 60 are two nodes, 62 and 64. The circle represents where the node is located and the tail represents where a traveler would come from to reach that node.
In FIG. 2A, The node symbol is displaced from the actual intersection for purposes of visibility. Links represent a path between nodes. For example, from node 64 a traveler can make a right turn at intersection 60 to enter road 54 or can proceed straight on road 50. Link 86 represents travel starting from intersection 60 on road 50 facing east, making a right turn at intersection 60 and proceeding south on road 54. Thus, link 86 connects node 64 to node 72.
FIG. 2A only shows links drawn for nodes 62 and 64. If links are drawn for all nodes, the directed graph would become too crowded and would be difficult to read. Thus, the directed graph is simplified and redrawn as in FIG. 2B.
The directed graph of FIG. 2B is used to symbolically represent the data structure stored for a map. A similar system may be utilized in any of the prior navigation systems. These systems do not actually store an image of a directed graph. Rather, a data structure representing the graph (or similar system) is stored. Each entry in the data structure represents a node. For each node, the data structure stores the location of the node (e.g., latitude and longitude), a list of neighboring nodes (nodes which can be traveled to via one link) and the various costs associated with getting to the neighboring nodes. The nodes and links are maintained in a database which is then searched to find routes in which to navigate the graph or network.
One general problem with navigation systems is that of how to search or determine the proper navigational route from the possible choices. This problem is particularly difficult when presented with a large network having many possible routes within which to navigate. However, once a network is known, systems for determining routes are also known. One example would be an application of Dijkstra""s Search Algorithm (E. W. Dijkstra, xe2x80x9cA Note on Two Problems in Connexion with Graphs,xe2x80x9d Numerische Mathematik, Vol. 1, pp. 269-271 [1959]) to the directed graph.
Poppen et al., U.S. patent application Ser. No. 08/802,733, filed Feb. 20,1997, entitled xe2x80x9cCACHING FOR PATHFINDING,xe2x80x9d incorporated herein by reference, in its entirety, teaches a system for determining routes for a directed graph. This and other route finding systems look at a network as a set of individual paths and piece together an acceptable route by iteratively and intelligently selecting and comparing possible routes.
One method for increasing the efficiency of the iterative route determination systems is to utilize a system of tiles representing an area (network) to be navigated. Such a system is described in Amakawa et al., U.S. Pat. 6,016,485, Ser. No. 09/023,504, filed Feb. 13, 1998, entitled xe2x80x9cA SYSTEM FOR PATHFINDING,xe2x80x9d incorporated herein by reference, in its entirety. Briefly described, the network is broken into tiles having plural entrance and exit nodes, which are then utilized as entrance and exit points to the tiles. Route planning within a tile does not change, but the routes between tiles are well known and quickly calculated. Thus navigation or route planning need only be calculated for travel within an origin tile and a destination tile.
Determining the cost of a particular route is also important to a successful navigation aid. Such cost may be measured in $ (tolls), gasoline, or time, for example. U.S. Pat. No. 5,729,458, entitled xe2x80x9cCOST ZONES,xe2x80x9d incorporated herein by reference, teaches about the use of costs.
The above-discussed technical innovations have led to modern mapping and navigation systems for automotive, marine, and other transport systems, that are cost efficient and provide quality, needed information to users. The above technologies are also applicable to computing networks and communications systems that also require route planning (telecom applications, static applications, Internet applications, PC applications, etc, for example).
However, in today""s fast paced environment many people do not necessarily have the time to learn new navigation systems. Even once learned, inputting starting locations and destinations can be time consuming and cumbersome. Even a simple mechanism for inputting a destination would necessarily divert some of a drivers attention from the task at hand (driving, for example). Sometimes the starting location and/or destination is not precisely known at the beginning of a trip.
Current routing, guidance, and map display systems only provide limited help to a driver who does not enter a destination. Furthermore, large amounts of real time traffic information is currently available via electronic communication and other means that provides relevant information that a driver would want to consider in determining a selected route. Such information is generally too abundant to be effectively displayed for consideration by the driver.
A navigation device would be very useful, and alleviate many of the problems in the prior art, if driving directions would be presented without a requirement of a destination. Roughly described, the present invention provides a navigational device that computes and displays driving directions and/or information to any of general destinations, including, but not limited to, any of the following: major cities, landmarks, streets, routes, waypoints, waypaths (such as a highway), and other general destinations without a specific destination or origin input requirement from a user.
The invention is particularly useful in a case where there are at least two possible destinations (and in general several). The invention gives a user information necessary (and at the appropriate time) to make decisions (choices between alternative general destinations). For example, suppose a user has agreed to take his sister-in-law to the airport. She lives in San Jose and the user knows how to get to her house but doesn""t know much about the overall road network in her neighborhood. The user arrives at the house and finds out that they need to go to Oakland airport, not San Jose airportxe2x80x94and they are late. The user proceeds in his/her car knowing that Oakland airport is near Oakland.
The invention tells the user how to get to Rte. 101 and Rte. 280 and the user knows that Rte. 101 will have highway connections to the East Bay, so the user heads toward Rte. 101. At Rte. 101, the invention tells the user that North is to SF and South is to Gilroy, and the user makes the decision to go north. Next, the invention tells the user that the user is approaching Rte. I-880 which proceeds North to Fremont, Hayward and Oakland or West to Los Gatos and Santa Cruz, or that the user can stay on Rte. 101 to Sunnyvale and San Francisco. This is enough information for the user to select Rte. 880, North. As the user gets reasonably close to Oakland airport, the invention presents a sign that tells the user how to exit to Oakland Airport. As the user takes that exit, the user is provided choices to other nearby points, but as long as the user keeps moving towards the Airport that choice is always in the list. Thus, the user gets to the airport without ever entering a destination and without ever selecting the airport.
By providing directions or other navigational aids to general destinations (rather than a specific address), the invention solves most practical navigation problems. The invention allows a user to get started towards a general destination (north on Rte. 101, for example), allowing the user to determine more specific directions (perhaps to a specific address) at a later time. Thus, instead of focusing on an enumerated endpoint (specific) destination, the present invention facilitates navigation, by focusing on an area near or encompassing a location where the user wants to travel. It is often the case that a driver knows where the end destination is but is missing knowledge about how to get, say, to the nearest highway entrance. The present invention provides driving information to such key waypoints without the need for any operator input.
In one embodiment, the present invention provides a device capable of providing routing information without user provided origin or destination requirements. In addition, simplified navigation directions and route information are automatically provided at relevant decision points. Such routing information may take the form of an in-car electronic sign that points in a relevant direction toward a major route, waypath, waypoint, city, landmark, previous destination, or other point, thoroughfare, etc. Routing without a user-specified origin or destination can be accomplished in similar fashion, and can be used to calculate various different routes toward a point of interest, such as a retail establishment. In one embodiment, an origin or a destination is provided, but not both.
In another embodiment, the present invention considers all available real time and other traffic information when providing the automatically generated driving guides.
In yet another embodiment, the present invention is a navigation device configured to display navigation directions from an origin (and updating as the origin changes position) without a destination requirement. The navigation directions may comprise a listing of routes and an indication of which direction the routes are from the origin. The indication includes an arrow pointing from the origin in a direction toward the route or other general destination.
The navigation device may be realized in a device comprised of a display mechanism, a computing unit connected to the display mechanism and configured to compute and provide navigation directions to the display mechanism without a destination requirement, including, an entrance/exit point module configured to determine a set of entrance and exit points based on predetermined selection factors, and a directions module configured to determine said navigation directions from the origin to each entrance and exit point.
The present invention can be implemented using software, hardware, or a combination of software and hardware. When all or portions of the present invention are implemented in software, that software can reside on a processor readable storage medium (media). Examples of appropriate processor readable storage medium (media) include a floppy disk, hard disk, CD ROM, memory IC, DVD, minidisc, etc. When the system includes hardware, the hardware may include an output device (e.g. a monitor, touch screen, telephone, speaker or printer), an input device (e.g. a keyboard, pointing device, touch screen, and/or a microphone), a processor in communication with the output device and processor readable storage medium in communication with the processor. The processor readable storage medium stores code capable of programming the processor to perform the steps to implement the present invention. The process of the present invention can also be implemented on a web page on the Internet or on a server that can be accessed over wired or wireless telephone lines, or other communications mediums.
The present invention includes a method of navigating, comprising the steps of computing navigation directions from an origin without specific destination requirements, and displaying the navigation directions. In one embodiment, the step of displaying includes the steps of listing a set of general locations and placing at least one directional indication to correspond with each location listed.
The present invention may also be utilized in a reverse manner to that described above, i.e., to find directions to a destination without an origin requirement. Such a system would calculate navigation or driving directions to the destination from each of major areas, cities, routes or arteries in a direction toward the destination. In one alternative, the system would have a set of stored potential origins and directions would be generated from a set of said potential origins that are closest to the current location.